package com.itheima.leetcode.od.b.graph;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * (B卷,200分)- 战场索敌（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 有一个大小是N*M的战场地图，被墙壁 '#' 分隔成大小不同的区域，上下左右四个方向相邻的空地 '.' 属于同一个区域，只有空地上可能存在敌人'E”，请求出地图上总共有多少区域里的敌人数小于K。
 * <p>
 * 输入描述
 * <p>
 * 第一行输入为N,M,K；
 * <p>
 * N表示地图的行数，M表示地图的列数， K表示目标敌人数量
 * N，M<=100
 * 之后为一个NxM大小的字符数组。
 * <p>
 * 输出描述
 * <p>
 * 敌人数小于K的区域数量
 * <p>
 * 用例
 * <p>
 * 输入	3 5 2
 * <p>
 * ..#EE
 * <p>
 * E.#E.
 * <p>
 * ###..
 * <p>
 * 输出	1
 * 说明	地图被墙壁分为两个区域，左边区域有1个敌人，右边区域有3个敌人，符合条件的区域数量是1
 */
public class DFSSearchingForEnemies {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int[] tmp = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = tmp[0];
        m = tmp[1];
        k = tmp[2];

        visited = new boolean[n][m];

        matrix = new char[n][];
        for (int i = 0; i < n; i++) {
            matrix[i] = sc.nextLine().toCharArray();
        }*/

        String input1 = "3 5 2";
        int[] tmp = Arrays.stream(input1.split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = tmp[0];
        int m = tmp[1];
        int k = tmp[2];

        String input2 = "..#EE\nE.#E.\n###..";
        char[][] matrix = Arrays.stream(input2.split("\n"))
                .map(s -> s.toCharArray())
                .toArray(char[][]::new);

        System.out.println(getResult(matrix, k));
    }

    // 上、下、左、右偏移量
    static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static int getResult(char[][] matrix, int k) {
        int n = matrix.length;
        int m = matrix[0].length;
        int ans = 0;
        boolean[][] visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (visited[i][j] || matrix[i][j] == '#') {
                    continue;
                }
                // 如果(i,j)位置未访问过，且不是墙，则进入广搜，广搜结果是广搜区域内的敌军数量，如果数量小于k，则该区域符合要求
                ans += bfs(i, j, matrix, visited) < k ? 1 : 0;
            }
        }

        return ans;
    }

    public static int bfs(int i, int j, char[][] matrix, boolean[][] visited) {
        int n = matrix.length;
        int m = matrix[0].length;
        // 该区域敌军数量
        int count = 0;

        // 标记该位置访问过
        visited[i][j] = true;

        // 如果对应位置是E，则敌军数量+1
        if (matrix[i][j] == 'E') {
            count += 1;
        }

        // 广搜依赖于队列结构，先进先出
        LinkedList<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});

        while (queue.size() > 0) {
            int[] pos = queue.removeFirst();
            int x = pos[0];
            int y = pos[1];

            // 遍历该位置的上下左右
            for (int[] offset : offsets) {
                int newX = x + offset[0];
                int newY = y + offset[1];

                // 如果新位置不越界，且未访问过，且不是墙，则继续广搜
                if (newX >= 0 && newX < n && newY >= 0 && newY < m
                        && !visited[newX][newY]
                        && matrix[newX][newY] != '#') {
                    // 标记该位置访问过
                    visited[newX][newY] = true;

                    // 如果对应位置是E，则敌军数量+1
                    if (matrix[newX][newY] == 'E') {
                        count += 1;
                    }

                    queue.add(new int[]{newX, newY});
                }
            }
        }

        return count;
    }
}